﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Tom.Algorithm
{
    public delegate double GeneticEvaluate<T> (T chromosome);

    // Remarks: only operations depends on data structure are defined here (i.e., not included "selection" which is date independent)
    public interface IGeneticOp<T>
    {
         T CreateInstance();
         T CopyInstance(T chromosome);

         List<T> Crossover(T parent1, T parent2);
         T Mutate(T chromosome);
    }

    // Population selector
    public interface IGeneticSelector<T>
    {
        void AssignPopulation(List<GeneticIndividual<T>> pop);
        GeneticIndividual<T> SelectForCrossover();
    }

    // Class to specific the individual in GA pop
    public class GeneticIndividual<T> : IComparable<GeneticIndividual<T>>
    {
        public readonly T Chromosome;
        public readonly double Evaluation;

        public GeneticIndividual(T chromosome, double evaluation) {
            this.Chromosome = chromosome;
            this.Evaluation = evaluation;
        }

        // Implement the comparison function
        public int CompareTo(GeneticIndividual<T> obj)
        {
            return Comparer<double>.Default.Compare(this.Evaluation, obj.Evaluation);
        }
    }

    // The GA engine
    public class GeneticEngine<T> 
    {
        // Unchangable members
        public readonly int PopSize;

        // GA Parameters (changable)
        public int NumReplace;
        public double CrossoverProb;

        // Selector (changable)
        public IGeneticSelector<T> Selector;

        // Stopping conditions
        public readonly List<IGeneticStopCond> StopConditions;

        // RNG
        protected Random _Rnd;

        // population and their fitnesses
        protected List<GeneticIndividual<T>> _Pop;

        // Constructor(s)
        public GeneticEngine(int popSize) : this(popSize, new Random()) {}

        public GeneticEngine(int popSize, int seed) : this(popSize, new Random(seed)) {}
        
        public GeneticEngine(int popSize, Random rnd)
        {
            // store memeber varibles
            this.PopSize = popSize;

            this._Rnd = rnd;
            this._Pop = new List<GeneticIndividual<T>>(popSize);

            // Assign default values
            this.NumReplace = (int) (popSize * 0.9);
            this.CrossoverProb = 0.95;

            // Stop conditions (default with 2 rules)
            this.StopConditions = new List<IGeneticStopCond>();
            StopConditions.Add(new NoChangeGeneticStop(10));
            StopConditions.Add(new MaxIterGeneticStop(1000));


            // Default selector and use same random number generator
            this.Selector = new GeneticSelectorRW<T>(_Rnd);
        }

        // Perform minization w.r.t. the input Ops and Func
        public GeneticIndividual<T> Minimize(IGeneticOp<T> op, GeneticEvaluate<T> func)
        {
            // Initialize the population
            InitPopulation(op, func);

            // Evolve until the any of stopping condition hit
            while (!IsDone())
            {
                // Assign the population to the selector
                Selector.AssignPopulation(_Pop);

                // Copy the whole previous population
                List<GeneticIndividual<T>> newPop = new List<GeneticIndividual<T>>(_Pop);

                // Keep (N - # Replace) unchanged
                int N = PopSize - NumReplace;

                // Apply crossover and mutation on remains population
                while (N < PopSize)
                {
                    T p1 = Selector.SelectForCrossover().Chromosome;
                    T p2 = Selector.SelectForCrossover().Chromosome;

                    // Perform crossover
                    List<T> offsprings;
                    if (_Rnd.NextDouble() < CrossoverProb)
                    {
                        offsprings = op.Crossover(p1, p2);
                    }
                    else
                    {
                        offsprings = new List<T>(2);
                        offsprings.Add(op.CopyInstance(p1));
                        offsprings.Add(op.CopyInstance(p2));
                    }

                    // Perform mutation
                    offsprings[0] = op.Mutate(offsprings[0]);
                    offsprings[1] = op.Mutate(offsprings[1]);

                    newPop[N + 0] = new GeneticIndividual<T>(offsprings[0], func(offsprings[0]));
                    if (N + 1 < _Pop.Count)
                        newPop[N + 1] = new GeneticIndividual<T>(offsprings[1], func(offsprings[1]));

                    N += 2;
                }

                // Replace with new pop
                _Pop = newPop;

                // Sort the new population
                _Pop.Sort();
            } 

            return _Pop[0];
        }

        // Init. the population
        protected void InitPopulation(IGeneticOp<T> op, GeneticEvaluate<T> func)
        {
            // Clear all existing elements
            _Pop.Clear();

            // Init. the population and their fitnesses
            for (int i = 0; i < PopSize; i++)
            {
                T chromosome = op.CreateInstance();
                double evaluation = func(chromosome);
                _Pop.Add(new GeneticIndividual<T>(chromosome, evaluation));
            }

            // Sort the population
            _Pop.Sort();
        }

        // Determine if the GA is done
        protected bool IsDone()
        {
            bool isDone = false;

            foreach (IGeneticStopCond cond in StopConditions)
            {
                if (cond.IsSatisfied(_Pop))
                {
                    isDone = true; break;
                }
            }

            return isDone;
        }
    }
}
